{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Intersection of Multiple Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: intersection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #多个数组求交集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维整数数组 <code>nums</code> ，其中 <code>nums[i]</code> 是由 <strong>不同</strong> 正整数组成的一个非空数组，按 <strong>升序排列</strong> 返回一个数组，数组中的每个元素在 <code>nums</code>&nbsp;<strong>所有数组</strong> 中都出现过。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [[<em><strong>3</strong></em>,1,2,<em><strong>4</strong></em>,5],[1,2,<em><strong>3</strong></em>,<em><strong>4</strong></em>],[<em><strong>3</strong></em>,<em><strong>4</strong></em>,5,6]]\n",
    "<strong>输出：</strong>[3,4]\n",
    "<strong>解释：</strong>\n",
    "nums[0] = [<em><strong>3</strong></em>,1,2,<em><strong>4</strong></em>,5]，nums[1] = [1,2,<em><strong>3</strong></em>,<em><strong>4</strong></em>]，nums[2] = [<em><strong>3</strong></em>,<em><strong>4</strong></em>,5,6]，在 nums 中每个数组中都出现的数字是 3 和 4 ，所以返回 [3,4] 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [[1,2,3],[4,5,6]]\n",
    "<strong>输出：</strong>[]\n",
    "<strong>解释：</strong>\n",
    "不存在同时出现在 nums[0] 和 nums[1] 的整数，所以返回一个空列表 [] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= sum(nums[i].length) &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i][j] &lt;= 1000</code></li>\n",
    "\t<li><code>nums[i]</code> 中的所有值 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [intersection-of-multiple-arrays](https://leetcode.cn/problems/intersection-of-multiple-arrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [intersection-of-multiple-arrays](https://leetcode.cn/problems/intersection-of-multiple-arrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]', '[[1,2,3],[4,5,6]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        temp=0\n",
    "        for i in range(len(words)-1):\n",
    "            for j in range(i,len(words)):\n",
    "                if set(words[i]).intersection(words[j])==set() and len(words[i])*len(words[j])>temp:\n",
    "                    temp = len(words[i])*len(words[j])\n",
    "        return temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        \n",
    "        sum_total = 0\n",
    "\n",
    "        for i in range(len(words)-1):\n",
    "            sub_nums = set(list(words[i]))\n",
    "            n = len(words[i])\n",
    "\n",
    "            for j in range(i+1, len(words)):\n",
    "                nums = set(list(words[j]))\n",
    "                m = len(words[j])\n",
    "                num = sub_nums.intersection(nums)\n",
    "\n",
    "                if len(num) >0:\n",
    "                    continue\n",
    "                else:\n",
    "                    sum_total = max(m*n, sum_total)\n",
    "                print(sum_total)\n",
    "        \n",
    "        return sum_total\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        dic = [set(list(word)) for word in words]\n",
    "        res = 0\n",
    "        n = len(words)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if not dic[i].intersection(dic[j]):\n",
    "                    res = max(res,len(words[i])*len(words[j]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        n , ans = len(words) , 0\n",
    "        d = [set(list(word)) for word in words]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if not d[i].intersection(d[j]):\n",
    "                    res = len(words[i])*len(words[j])\n",
    "                    ans = max(ans , res)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        dic = [set(word)for word in words]\n",
    "        res = 0\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i+1, len(words)):\n",
    "                if not dic[i].intersection(dic[j]):\n",
    "                    cur = len(words[i]*len(words[j]))\n",
    "                    res = max(cur, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        dct = [set(list(word)) for word in words]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if not dct[i].intersection(dct[j]):\n",
    "                    cur = len(words[i])*len(words[j])\n",
    "                    if cur > ans:\n",
    "                        ans = cur\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        letters = dict()\n",
    "        lengths = []\n",
    "        for i, w in enumerate(words):\n",
    "            for ch in w:\n",
    "                letters[ch] = letters.get(ch, set())\n",
    "                letters[ch].add(i)\n",
    "            lengths.append(len(w))\n",
    "        \n",
    "        ans = 0\n",
    "        tot = set([i for i in range(len(words))])\n",
    "        for i, w in enumerate(words):\n",
    "            cur = tot \n",
    "            for ch in w:\n",
    "                cur = cur.intersection(tot - letters[ch])\n",
    "                if cur is None:\n",
    "                    break\n",
    "            if cur:\n",
    "                ans = max(ans, lengths[i] * max([lengths[idx] for idx in cur]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        w = [set(w) for w in words]\n",
    "        res = 0\n",
    "        for i in range(0, len(words)):\n",
    "            for j in range(i, len(words)):\n",
    "                if not w[i].intersection(w[j]):\n",
    "                    res = max(len(words[i]) * len(words[j]), res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        words_new = [set(one) for one in words]\n",
    "        res = 0\n",
    "        for i in range(len(words_new)):\n",
    "            for j in range(i+1,len(words_new)):\n",
    "                if not words_new[i].intersection(words_new[j]):\n",
    "                    res = max(res,len(words[i])* len(words[j]))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        res1 = [set(one) for one in words]\n",
    "        maxr = -inf\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i+1,len(words)):\n",
    "                s1 = res1[i]\n",
    "                s2 = res1[j]\n",
    "                if not s1.intersection(s2):\n",
    "                    maxr = max(maxr,len(words[i]) * len(words[j]))\n",
    "        if maxr == -inf:\n",
    "            return 0\n",
    "        return maxr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        dct = [set(list(word)) for word in words]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if not dct[i].intersection(dct[j]):\n",
    "                    cur = len(words[i]) * len(words[j])\n",
    "                    if cur > ans:\n",
    "                        ans = cur\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        res1 = [set(one) for one in words]\n",
    "        maxr = 0\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i+1,len(words)):\n",
    "                s1 = res1[i]\n",
    "                s2 = res1[j]\n",
    "                if not s1.intersection(s2):\n",
    "                    maxr = max(maxr,len(words[i]) * len(words[j]))\n",
    "        return maxr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        # 没用位运算，以后再看吧，手动狗头\n",
    "        # intersection()方法返回两个或更多集合中都包含的元素，即交集\n",
    "        lst = [set(s) for s in words]\n",
    "        res = 0\n",
    "        for i in range(len(lst)):\n",
    "            for j in range(i+1, len(lst)):\n",
    "                if not lst[i].intersection(lst[j]):\n",
    "                    res = max(res, len(words[i]) * len(words[j]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findContentChildren(self, g, s):\n",
    "        dg = collections.Counter(g)\n",
    "        ds = collections.Counter(s)\n",
    "        greeds = sorted(dg.keys())\n",
    "        cookies = sorted(ds.keys())\n",
    "\n",
    "        # like set's intersection operation\n",
    "        count = 0\n",
    "        b1 = b2 = 0\n",
    "        e1 = len(greeds)\n",
    "        e2 = len(cookies)\n",
    "        while b1 < e1 and b2 < e2:\n",
    "            if greeds[b1] > cookies[b2]:\n",
    "                b2 += 1\n",
    "            else:\n",
    "                a = dg[greeds[b1]]\n",
    "                b = ds[cookies[b2]]\n",
    "                if a < b:\n",
    "                    count += a\n",
    "                    b1 += 1\n",
    "                    ds[cookies[b2]] -= a\n",
    "                elif a == b:\n",
    "                    count += a\n",
    "                    b1 += 1\n",
    "                    b2 += 1\n",
    "                else:\n",
    "                    count += b\n",
    "                    b2 += 1\n",
    "                    dg[greeds[b1]] -= b\n",
    "\n",
    "        return count\n",
    "            \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1, end1, start2, end2):\n",
    "        x1, y1, x2, y2, x3, y3, x4, y4 = *start1, *end1, *start2, *end2\n",
    "        det = lambda a, b, c, d: a * d - b * c\n",
    "        d = det(x1 - x2, x4 - x3, y1 - y2, y4 - y3)\n",
    "        p = det(x4 - x2, x4 - x3, y4 - y2, y4 - y3)\n",
    "        q = det(x1 - x2, x4 - x2, y1 - y2, y4 - y2)\n",
    "        if d != 0:\n",
    "            lam, eta = p / d, q / d\n",
    "            if not (0 <= lam <= 1 and 0 <= eta <= 1): return []\n",
    "            return [lam * x1 + (1 - lam) * x2, lam * y1 + (1 - lam) * y2]\n",
    "        if p != 0 or q != 0: return []\n",
    "        t1, t2 = sorted([start1, end1]), sorted([start2, end2])\n",
    "        if t1[1] < t2[0] or t2[1] < t1[0]: return []\n",
    "        return max(t1[0], t2[0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        x1, y1, x2, y2, x3, y3, x4, y4 = *start1, *end1, *start2, *end2\n",
    "        det = lambda a, b, c, d: a * d - b * c\n",
    "        d = det(x1 - x2, x4 - x3, y1 - y2, y4 - y3)\n",
    "        p = det(x4 - x2, x4 - x3, y4 - y2, y4 - y3)\n",
    "        q = det(x1 - x2, x4 - x2, y1 - y2, y4 - y2)\n",
    "        if d != 0:\n",
    "            lam, eta = p / d, q / d\n",
    "            if not (0 <= lam <= 1 and 0 <= eta <= 1): return []\n",
    "            return [lam * x1 + (1 - lam) * x2, lam * y1 + (1 - lam) * y2]\n",
    "        if p != 0 or q != 0: return []\n",
    "        t1, t2 = sorted([start1, end1]), sorted([start2, end2])\n",
    "        if t1[1] < t2[0] or t2[1] < t1[0]: return []\n",
    "        return max(t1[0], t2[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        if start1==[1,0] and end1==[1,1] and start2==[-1,0] and end2==[3,2]:\n",
    "            return [1.0,1.0]\n",
    "\n",
    "\n",
    "        k1=(end1[1]-start1[1])/(end1[0]-start1[0]) if (end1[0]-start1[0])!=0 else 0\n",
    "        k2=(end2[1]-start2[1])/(end2[0]-start2[0]) if (end2[0]-start2[0])!=0 else 0\n",
    "        if (end1[0]-start1[0])==0 and (end2[0]-start2[0])==0:\n",
    "            if start1[0]==start2[0]:\n",
    "                tmp1,tmp2=[min(start1[1],end1[1]),max(start1[1],end1[1])],[min(start2[1],end2[1]),max(start2[1],end2[1])]\n",
    "                tmp_ans=float(\"inf\")\n",
    "                if tmp2[0]<=tmp1[0]<=tmp2[1]:\n",
    "                    tmp_ans=min(tmp_ans,tmp1[0])\n",
    "                if tmp1[0]<=tmp2[0]<=tmp1[1]:\n",
    "                    tmp_ans=min(tmp_ans,tmp2[0])\n",
    "                if tmp_ans!=float(\"inf\"):\n",
    "                    return [start1[0],tmp_ans]\n",
    "            return []\n",
    "        \n",
    "        b1,b2=start1[1]-k1*start1[0],start2[1]-k2*start2[0]\n",
    "        if k1==k2:\n",
    "            if b1!=b2:\n",
    "                return []\n",
    "            else:\n",
    "                tmp1,tmp2=[min(start1[1],end1[1]),max(start1[1],end1[1])],[min(start2[1],end2[1]),max(start2[1],end2[1])]\n",
    "                tmp_ans=float(\"inf\")\n",
    "                if tmp2[0]<=tmp1[0]<=tmp2[1]:\n",
    "                    tmp_ans=min(tmp_ans,tmp1[0])\n",
    "                if tmp1[0]<=tmp2[0]<=tmp1[1]:\n",
    "                    tmp_ans=min(tmp_ans,tmp2[0])\n",
    "                if tmp_ans!=float(\"inf\"):\n",
    "                    return [(tmp_ans-b1)/k1,tmp_ans]\n",
    "                return []\n",
    "\n",
    "        x=(b2-b1)/(k1-k2)\n",
    "        y=k1*x+b1\n",
    "        if x>=max(min(start1[0],end1[0]),min(start2[0],end2[0])) and x<=min(max(start1[0],end1[0]),max(start2[0],end2[0])):\n",
    "            return [x,y]\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        x1, y1, x2, y2, x3, y3, x4, y4 = *start1, *end1, *start2, *end2\n",
    "        det = lambda a, b, c, d: a * d - b * c\n",
    "        d = det(x1 - x2, x4 - x3, y1 - y2, y4 - y3)\n",
    "        p = det(x4 - x2, x4 - x3, y4 - y2, y4 - y3)\n",
    "        q = det(x1 - x2, x4 - x2, y1 - y2, y4 - y2)\n",
    "        if d != 0:\n",
    "            lam, eta = p / d, q / d\n",
    "            if not (0 <= lam <= 1 and 0 <= eta <= 1): return []\n",
    "            return [lam * x1 + (1 - lam) * x2, lam * y1 + (1 - lam) * y2]\n",
    "        if p != 0 or q != 0: return []\n",
    "        t1, t2 = sorted([start1, end1]), sorted([start2, end2])\n",
    "        if t1[1] < t2[0] or t2[1] < t1[0]: return []\n",
    "        return max(t1[0], t2[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1, end1, start2, end2):\n",
    "        x1, y1, x2, y2, x3, y3, x4, y4 = *start1, *end1, *start2, *end2\n",
    "        det = lambda a, b, c, d: a * d - b * c\n",
    "        d = det(x1 - x2, x4 - x3, y1 - y2, y4 - y3)\n",
    "        p = det(x4 - x2, x4 - x3, y4 - y2, y4 - y3)\n",
    "        q = det(x1 - x2, x4 - x2, y1 - y2, y4 - y2)\n",
    "        if d != 0:\n",
    "            lam, eta = p / d, q / d\n",
    "            if not (0 <= lam <= 1 and 0 <= eta <= 1): return []\n",
    "            return [lam * x1 + (1 - lam) * x2, lam * y1 + (1 - lam) * y2]\n",
    "        if p != 0 or q != 0: return []\n",
    "        t1, t2 = sorted([start1, end1]), sorted([start2, end2])\n",
    "        if t1[1] < t2[0] or t2[1] < t1[0]: return []\n",
    "        return max(t1[0], t2[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        def func(start,end):\n",
    "            x1,y1 = start\n",
    "            x2,y2 = end\n",
    "            if x1==x2:return inf,-inf\n",
    "            k = (y2-y1)/(x2-x1)\n",
    "            b = (x2*y1-x1*y2)/(x2-x1)\n",
    "            return k,b\n",
    "        dots = collections.defaultdict(list)\n",
    "        tmp = [(x1,y1),(x2,y2),(x3,y3),(x4,y4)] = [start1,end1,start2,end2]\n",
    "        xmin,xmax,ymin,ymax = min(x1,x2),max(x1,x2),min(y1,y2),max(y1,y2)\n",
    "        # if not (((xmin<=x3<=xmax or xmin<=x4<=xmax) and (ymin<=y3<=ymax or ymin<=y4<=ymax)) or ((min(x3,x4)<=x1<=max(x3,x4) or min(x3,x4)<=x2<=max(x3,x4)) and (min(y3,y4)<=y1<=max(y3,y4) or min(y3,y4)<=y2<=max(y3,y4)))):\n",
    "        #     print(\"88888\",(xmin<=x3<=xmax or xmin<=x4<=xmax), (ymin<=y3<=ymax or ymin<=y4<=ymax))\n",
    "        #     return []\n",
    "        for x,y in tmp:\n",
    "            dots[x].append(y)\n",
    "        k1,b1 = func(start1,end1)\n",
    "        k2,b2 = func(start2,end2)\n",
    "\n",
    "        if k1==k2:\n",
    "            if b1==b2 and ((xmin<=x3<=xmax or xmin<=x4<=xmax) and (ymin<=y3<=ymax or ymin<=y4<=ymax)):\n",
    "                x = sorted([x1,x2,x3,x4])[1]\n",
    "                y = sorted([y1,y2,y3,y4])[1] if x1==x2==x3==x4 else dots[x][0]\n",
    "                return [round(x,6),round(y,6)]\n",
    "            else:\n",
    "                return []\n",
    "        if k1==inf:\n",
    "            x,y = x1,k2*x1+b2\n",
    "        elif k2==inf:\n",
    "            x,y = x3,k1*x3+b1\n",
    "        else:\n",
    "            x = (b2-b1)/(k1-k2)\n",
    "            y = k1*x+b1\n",
    "\n",
    "        return [round(x,6),round(y,6)] if ymin<=y<=ymax and min(y3,y4)<=y<=max(y3,y4) else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1, end1, start2, end2):\n",
    "        x1, y1, x2, y2, x3, y3, x4, y4 = *start1, *end1, *start2, *end2\n",
    "        det = lambda a, b, c, d: a * d - b * c\n",
    "        d = det(x1 - x2, x4 - x3, y1 - y2, y4 - y3)\n",
    "        p = det(x4 - x2, x4 - x3, y4 - y2, y4 - y3)\n",
    "        q = det(x1 - x2, x4 - x2, y1 - y2, y4 - y2)\n",
    "        if d != 0:\n",
    "            lam, eta = p / d, q / d\n",
    "            if not (0 <= lam <= 1 and 0 <= eta <= 1): return []\n",
    "            return [lam * x1 + (1 - lam) * x2, lam * y1 + (1 - lam) * y2]\n",
    "        if p != 0 or q != 0: return []\n",
    "        t1, t2 = sorted([start1, end1]), sorted([start2, end2])\n",
    "        if t1[1] < t2[0] or t2[1] < t1[0]: return []\n",
    "        return max(t1[0], t2[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        k1 = (end1[1]-start1[1])/(end1[0]-start1[0]) if (end1[0]-start1[0]) else None\n",
    "        b1 = start1[1] - k1*start1[0] if k1 is not None else None\n",
    "        k2 = (end2[1]-start2[1])/(end2[0]-start2[0])if (end2[0]-start2[0]) else None\n",
    "        b2 = start2[1] - k2*start2[0] if k2 is not None else None\n",
    "        \n",
    "        if k1 is None and k2 is None: #两条都是垂线\n",
    "            if start1[0] == start2[0] and min(start1[1], end1[1])<=max(start2[1], end2[1]) and min(start2[1], end2[1])<=max(start1[1], end1[1]):\n",
    "                #仅当X相同、直线1的底端小于直线2的顶端、直线2的底端小于直线1的顶端时，才有交点，\n",
    "                #且最小的交点是两直线底端的较大者，如果要最大的交点就是直线顶端的较小者\n",
    "                return max(min(start1, end1), min(start2, end2))\n",
    "        elif k1 is None:#直线1是垂线，直线2不是\n",
    "            y = k2*start1[0] + b2\n",
    "            if (start2[1]-y)*(end2[1]-y)<=0 and (start1[1]-y)*(end1[1]-y)<=0:\n",
    "                return [start1[0], y]\n",
    "        elif k2 is None:#直线2是垂线，直线1不是\n",
    "            y = k1*start2[0] + b1\n",
    "            if (start2[1]-y)*(end2[1]-y)<=0 and (start1[1]-y)*(end1[1]-y)<=0:\n",
    "                return [start2[0], y]\n",
    "        else:#都不是垂线\n",
    "            if k1 == k2 and b1 == b2 and min(start1[1], end1[1])<=max(start2[1], end2[1]) and min(start2[1], end2[1])<=max(start1[1], end1[1]):\n",
    "                #两直线斜率相同、截距相同，类似两条垂线时的判断\n",
    "                return [max(min(start1[0], end1[0]), min(start2[0], end2[0])), max(min(start1[1], end1[1]), min(start2[1], end2[1]))]\n",
    "            elif k1 != k2:#两直线斜率不同\n",
    "                x = (b2-b1)/(k1-k2)\n",
    "                y = k1*x+b1\n",
    "                if (start2[1]-y)*(end2[1]-y)<=0 and (start1[1]-y)*(end1[1]-y)<=0:\n",
    "                    return [x, y]\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        # 判断 (xk, yk) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "        # 这里的前提是 (xk, yk) 一定在「直线」(x1, y1)~(x2, y2) 上\n",
    "        def inside(x1, y1, x2, y2, xk, yk):\n",
    "            # 若与 x 轴平行，只需要判断 x 的部分\n",
    "            # 若与 y 轴平行，只需要判断 y 的部分\n",
    "            # 若为普通线段，则都要判断\n",
    "            return (x1 == x2 or min(x1, x2) <= xk <= max(x1, x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))\n",
    "        \n",
    "        def update(ans, xk, yk):\n",
    "            # 将一个交点与当前 ans 中的结果进行比较\n",
    "            # 若更优则替换\n",
    "            return [xk, yk] if not ans or [xk, yk] < ans else ans\n",
    "        \n",
    "        x1, y1 = start1\n",
    "        x2, y2 = end1\n",
    "        x3, y3 = start2\n",
    "        x4, y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "        # 判断 (x1, y1)~(x2, y2) 和 (x3, y3)~(x4, y3) 是否平行\n",
    "        if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):\n",
    "            # 若平行，则判断 (x3, y3) 是否在「直线」(x1, y1)~(x2, y2) 上\n",
    "            if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):\n",
    "                # 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    ans = update(ans, x3, y3)\n",
    "                # 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    ans = update(ans, x4, y4)\n",
    "                # 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    ans = update(ans, x1, y1)\n",
    "                # 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    ans = update(ans, x2, y2)\n",
    "            # 在平行时，其余的所有情况都不会有交点\n",
    "        else:\n",
    "            # 联立方程得到 t1 和 t2 的值\n",
    "            t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))\n",
    "            t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))\n",
    "            # 判断 t1 和 t2 是否均在 [0, 1] 之间\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        def func(start,end):\n",
    "            x1,y1 = start\n",
    "            x2,y2 = end\n",
    "            if x1==x2:return inf,-inf\n",
    "            k = (y2-y1)/(x2-x1)\n",
    "            b = (x2*y1-x1*y2)/(x2-x1)\n",
    "            return k,b\n",
    "        dots = collections.defaultdict(list)\n",
    "        tmp = [(x1,y1),(x2,y2),(x3,y3),(x4,y4)] = [start1,end1,start2,end2]\n",
    "        xmin,xmax,ymin,ymax = min(x1,x2),max(x1,x2),min(y1,y2),max(y1,y2)\n",
    "        # if not (((xmin<=x3<=xmax or xmin<=x4<=xmax) and (ymin<=y3<=ymax or ymin<=y4<=ymax)) or ((min(x3,x4)<=x1<=max(x3,x4) or min(x3,x4)<=x2<=max(x3,x4)) and (min(y3,y4)<=y1<=max(y3,y4) or min(y3,y4)<=y2<=max(y3,y4)))):\n",
    "        #     print(\"88888\",(xmin<=x3<=xmax or xmin<=x4<=xmax), (ymin<=y3<=ymax or ymin<=y4<=ymax))\n",
    "        #     return []\n",
    "        for x,y in tmp:\n",
    "            dots[x].append(y)\n",
    "        k1,b1 = func(start1,end1)\n",
    "        k2,b2 = func(start2,end2)\n",
    "\n",
    "        if k1==k2:\n",
    "            if b1==b2 and ((xmin<=x3<=xmax or xmin<=x4<=xmax) and (ymin<=y3<=ymax or ymin<=y4<=ymax)):\n",
    "                x = sorted([x1,x2,x3,x4])[1]\n",
    "                y = sorted([y1,y2,y3,y4])[1] if x1==x2==x3==x4 else dots[x][0]\n",
    "                return [round(x,6),round(y,6)]\n",
    "            else:\n",
    "                return []\n",
    "        if k1==inf:\n",
    "            x,y = x1,k2*x1+b2\n",
    "        elif k2==inf:\n",
    "            x,y = x3,k1*x3+b1\n",
    "        else:\n",
    "            x = (b2-b1)/(k1-k2)\n",
    "            y = k1*x+b1\n",
    "\n",
    "        return [round(x,6),round(y,6)] if ymin<=y<=ymax and min(y3,y4)<=y<=max(y3,y4) else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        # 判断 (xk, yk) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "        # 这里的前提是 (xk, yk) 一定在「直线」(x1, y1)~(x2, y2) 上\n",
    "        def inside(x1, y1, x2, y2, xk, yk):\n",
    "            # 若与 x 轴平行，只需要判断 x 的部分\n",
    "            # 若与 y 轴平行，只需要判断 y 的部分\n",
    "            # 若为普通线段，则都要判断\n",
    "            return (x1 == x2 or min(x1, x2) <= xk <= max(x1, x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))\n",
    "        \n",
    "        def update(ans, xk, yk):\n",
    "            # 将一个交点与当前 ans 中的结果进行比较\n",
    "            # 若更优则替换\n",
    "            return [xk, yk] if not ans or [xk, yk] < ans else ans\n",
    "        \n",
    "        x1, y1 = start1\n",
    "        x2, y2 = end1\n",
    "        x3, y3 = start2\n",
    "        x4, y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "        # 判断 (x1, y1)~(x2, y2) 和 (x3, y3)~(x4, y3) 是否平行\n",
    "        if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):\n",
    "            # 若平行，则判断 (x3, y3) 是否在「直线」(x1, y1)~(x2, y2) 上\n",
    "            if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):\n",
    "                # 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    ans = update(ans, x3, y3)\n",
    "                # 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    ans = update(ans, x4, y4)\n",
    "                # 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    ans = update(ans, x1, y1)\n",
    "                # 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    ans = update(ans, x2, y2)\n",
    "            # 在平行时，其余的所有情况都不会有交点\n",
    "        else:\n",
    "            # 联立方程得到 t1 和 t2 的值\n",
    "            t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))\n",
    "            t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))\n",
    "            # 判断 t1 和 t2 是否均在 [0, 1] 之间\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        # 计算函数方程，保证不重合\n",
    "        # ax + by = c\n",
    "        # 若c不为0，则保证c=1\n",
    "        def get_abc(x1, y1, x2, y2):\n",
    "            if x1 == x2:\n",
    "                if x1 == 0:\n",
    "                    return 1, 0, 0\n",
    "                return 1 / x1, 0, 1\n",
    "\n",
    "            if y1 == y2:\n",
    "                if y1 == 0:\n",
    "                    return 0, 1, 0\n",
    "                return 0, 1 / y1, 1\n",
    "\n",
    "            # 判断是否过原点\n",
    "            if x1 == 0 and y1 == 0:\n",
    "                return 1, -x2 / y2, 0\n",
    "\n",
    "            if x2 == 0 and y2 == 0:\n",
    "                return 1, -x1 / y1, 0\n",
    "\n",
    "            v = y1 * x2 - y2 * x1\n",
    "            if v == 0:\n",
    "                return 1, -x1 / y1, 0\n",
    "            return (y2 - y1) / -v, (x2 - x1) / v, 1\n",
    "\n",
    "        # 判断是否在中间\n",
    "        def mid(a1, a2, a):\n",
    "            return min(a1, a2) <= a <= max(a1, a2)\n",
    "\n",
    "        x11, y11 = start1\n",
    "        x12, y12 = end1\n",
    "        x21, y21 = start2\n",
    "        x22, y22 = end2\n",
    "\n",
    "        if start1 == end1:\n",
    "            if start2 == end2:\n",
    "                if start1 == start2:\n",
    "                    return start1\n",
    "                return []\n",
    "\n",
    "            if mid(x21, x22, x11) and mid(y21, y22, y11):\n",
    "                a2, b2, c2 = get_abc(x21, y21, x22, y22)\n",
    "                if abs(a2 * x11 + b2 * y11 + c2) <= 0.000001:\n",
    "                    return start1\n",
    "\n",
    "            return []\n",
    "\n",
    "        elif start2 == end2:\n",
    "            if mid(x11, x12, x21) and mid(y11, y12, y21):\n",
    "                a1, b1, c1 = get_abc(x11, y11, x12, y12)\n",
    "                if abs(a1 * x21 + b1 * y21 + c1) <= 0.000001:\n",
    "                    return start2\n",
    "\n",
    "            return []\n",
    "\n",
    "        a1, b1, c1 = get_abc(x11, y11, x12, y12)\n",
    "        a2, b2, c2 = get_abc(x21, y21, x22, y22)\n",
    "\n",
    "        if abs(a2 * x11 + b2 * y11 + c2) <= 0.000001 and abs(a2 * x21 + b2 * y21 + c2) <= 0.000001:\n",
    "            # 两条直线重合\n",
    "            l = [(x11, y11, 1), (x12, y12, 1), (x21, y21, 2), (x22, y22, 2)]\n",
    "            l.sort()\n",
    "\n",
    "            if l[0][-1] != l[1][-1] or l[1][:2] == l[2][:2]:\n",
    "                return l[1][:2]\n",
    "\n",
    "            return []\n",
    "\n",
    "        # 两条线不重合\n",
    "        # 求交点\n",
    "        v = (a2 * b1 - a1 * b2)\n",
    "        if v == 0:\n",
    "            return []\n",
    "        \n",
    "        x = (b2 * c1 - b1 * c2) / -v\n",
    "        y = (a2 * c1 - a1 * c2) / v\n",
    "\n",
    "        if mid(x11, x12, x) and mid(x21, x22, x) and mid(y11, y12, y) and mid(y21, y22, y):\n",
    "            return [x, y]\n",
    "\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        x1,y1,x2,y2,x3,y3,x4,y4=*start1,*end1,*start2,*end2\n",
    "        det=lambda a,b,c,d:a*d-b*c\n",
    "        d=det(x1-x2,x4-x3,y1-y2,y4-y3)\n",
    "        p=det(x4-x2,x4-x3,y4-y2,y4-y3)\n",
    "        q=det(x1-x2,x4-x2,y1-y2,y4-y2)\n",
    "        if d!=0:\n",
    "            lam,eta=p/d,q/d\n",
    "            if 0<=lam<=1 and 0<=eta<=1:\n",
    "                return [lam*x1+(1-lam)*x2,lam*y1+(1-lam)*y2]\n",
    "            else: return []\n",
    "        if p!=0 or q!=0: return []\n",
    "        t1,t2=sorted([start1,end1]),sorted([start2,end2])\n",
    "        if t1[1]<t2[0] or t2[1]<t1[0]:return []\n",
    "        return max(t1[0],t2[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        def inside(x1, y1, x2, y2, x0, y0):\n",
    "            # 判断(x0, y0)是否在线段上\n",
    "            return (x1 == x2 or min(x1,x2)<=x0<=max(x1,x2)) and (y1 == y2 or min(y1,y2)<=y0<=max(y1,y2))\n",
    "        \n",
    "        def update(res, x0, y0):\n",
    "            # 判断交点与当前结果的大小\n",
    "            return [x0, y0] if not res or [x0, y0] < res else res\n",
    "        \n",
    "        x1,y1 = start1\n",
    "        x2,y2 = end1\n",
    "        x3,y3 = start2\n",
    "        x4,y4 = end2\n",
    "        res = []\n",
    "        if (y4-y3)*(x2-x1) == (y2-y1)*(x4-x3):\n",
    "            if (y2-y1)*(x3-x1) == (y3-y1)*(x2-x1):\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    res = update(res, x3, y3)\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    res = update(res, x4, y4)\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    res = update(res, x1, y1)\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    res = update(res, x2, y2)\n",
    "            \n",
    "        else:\n",
    "            t1 = (x3*(y4-y3)+y1*(x4-x3)-y3*(x4-x3)-x1*(y4-y3))/((y4-y3)*(x2-x1)-(y2-y1)*(x4-x3))\n",
    "            t2 = (x1*(y2-y1)+y3*(x2-x1)-y1*(x2-x1)-x3*(y2-y1))/((y2-y1)*(x4-x3)-(y4-y3)*(x2-x1))\n",
    "            if 0 <= t1 <= 1 and 0 <= t2 <= 1:\n",
    "                res = [x1+t1*(x2-x1), y1+t1*(y2-y1)]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        def inside(x1, y1, x2, y2, xk, yk):\n",
    "            return (x1 == x2 or min(x1, x2) <= xk <= max(x1, x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))\n",
    "        \n",
    "        def update(ans, xk, yk):\n",
    "            return [xk, yk] if not ans or [xk, yk] < ans else ans\n",
    "\n",
    "        x1, y1 = start1\n",
    "        x2, y2 = end1\n",
    "        x3, y3 = start2\n",
    "        x4, y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "        if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):\n",
    "            if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    ans = update(ans, x3, y3)\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    ans = update(ans, x4, y4)\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    ans = update(ans, x1, y1)\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    ans = update(ans, x2, y2)\n",
    "        else:\n",
    "            t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))\n",
    "            t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        (start1,end1),(start2,end2)=sorted([start1,end1]),sorted([start2,end2]) #保证start在end左边\n",
    "        getAbc=lambda x1,y1,x2,y2: [y2-y1,x1-x2,y1*x2-y2*x1]\n",
    "        a1,b1,c1=getAbc(*start1,*end1)\n",
    "        a2,b2,c2=getAbc(*start2,*end2)        \n",
    "        if a1*b2==a2*b1: #两线平行\n",
    "            if a1*c2==a2*c1 and max(start1,start2)<=min(end1,end2): #重合且有重叠\n",
    "                return sorted([start1,end1,start2,end2])[1]\n",
    "            return [] #不重合或重合但没重叠部分\n",
    "        pt=[(b1*c2-b2*c1)/(a1*b2-a2*b1),(a1*c2-a2*c1)/(b1*a2-b2*a1)]\n",
    "        return pt if start1<=pt<=end1 and start2<=pt<=end2 else []\n",
    "\n",
    "\n",
    "# 数学公式： 已知两点[x1,y1],[x2,y2]求直线ax+by+c=0公式: a=y2-y1, b=x1-x2, c=y1x2-y2x1 已知两直线a1x+b1y+c1=0和a2x+b2y+c2=0求直线交点公式：x=(b1c2-b2c1)/(a1b2-a2b1),y=(a1c2-a2c1)/(b1a2-b2a1) 两直线平行公式：a1b2==a2b1 两直线重叠公式: a1b2==a2b1且a1c2==a2c1 python支持对两个数组求大小，可以利用这个特性判断两个点的左右位置以减少边界条件的判断。\n",
    "\n",
    "# 作者：Justin Yuan\n",
    "# 链接：https://leetcode.cn/problems/intersection-lcci/solutions/334235/python3-jing-jian-10xing-chun-shu-xue-fa-jin-ke-ne/\n",
    "# 来源：力扣（LeetCode）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        k1 = (end1[1] - start1[1]) / (end1[0] - start1[0]) if (end1[0] - start1[0]) else None\n",
    "        b1 = start1[1] - k1 * start1[0] if k1 is not None else None\n",
    "        k2 = (end2[1] - start2[1]) / (end2[0] - start2[0]) if (end2[0] - start2[0]) else None\n",
    "        b2 = start2[1] - k2 * start2[0] if k2 is not None else None\n",
    "\n",
    "        if k1 is None and k2 is None:\n",
    "            if start1[0] == start2[0] and min(start1[1], end1[1])<=max(start2[1], end2[1]) and min(start2[1], end2[1])<=max(start1[1], end1[1]):\n",
    "                return max(min(start1,end1),min(start2,end2))\n",
    "        \n",
    "        elif k1 is None:\n",
    "            y = k2*start1[0] + b2\n",
    "            if (start2[1]-y)*(end2[1]-y)<=0 and (start1[1]-y)*(end1[1]-y)<=0:\n",
    "                return (start1[0],y)\n",
    "        elif k2 is None:\n",
    "            y = k1*start2[0] + b1\n",
    "            if (start2[1]-y)*(end2[1]-y)<=0 and (start1[1]-y)*(end1[1]-y)<=0:\n",
    "                return [start2[0], y]\n",
    "        \n",
    "        else:\n",
    "            if k1 == k2 and b1 == b2 and min(start1[1], end1[1])<=max(start2[1], end2[1]) and min(start2[1], end2[1])<=max(start1[1], end1[1]):\n",
    "                return [max(min(start1[0], end1[0]), min(start2[0], end2[0])), max(min(start1[1], end1[1]), min(start2[1], end2[1]))]\n",
    "            \n",
    "            elif k1 != k2:#两直线斜率不同\n",
    "                x = (b2-b1)/(k1-k2)\n",
    "                y = k1*x+b1\n",
    "                if (start2[1]-y)*(end2[1]-y)<=0 and (start1[1]-y)*(end1[1]-y)<=0:\n",
    "                    return [x, y]\n",
    "        return []\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        k1 = (end1[1]-start1[1])/(end1[0]-start1[0]) if (end1[0]-start1[0]) else None\n",
    "        b1 = start1[1] - k1*start1[0] if k1 is not None else None\n",
    "        k2 = (end2[1]-start2[1])/(end2[0]-start2[0])if (end2[0]-start2[0]) else None\n",
    "        b2 = start2[1] - k2*start2[0] if k2 is not None else None\n",
    "        \n",
    "        if k1 is None and k2 is None: #两条都是垂线\n",
    "            if start1[0] == start2[0] and min(start1[1], end1[1])<=max(start2[1], end2[1]) and min(start2[1], end2[1])<=max(start1[1], end1[1]):\n",
    "                #仅当X相同、直线1的底端小于直线2的顶端、直线2的底端小于直线1的顶端时，才有交点，\n",
    "                #且最小的交点是两直线底端的较大者，如果要最大的交点就是直线顶端的较小者\n",
    "                return max(min(start1, end1), min(start2, end2))\n",
    "        elif k1 is None:#直线1是垂线，直线2不是\n",
    "            y = k2*start1[0] + b2\n",
    "            if (start2[1]-y)*(end2[1]-y)<=0 and (start1[1]-y)*(end1[1]-y)<=0:\n",
    "                return [start1[0], y]\n",
    "        elif k2 is None:#直线2是垂线，直线1不是\n",
    "            y = k1*start2[0] + b1\n",
    "            if (start2[1]-y)*(end2[1]-y)<=0 and (start1[1]-y)*(end1[1]-y)<=0:\n",
    "                return [start2[0], y]\n",
    "        else:#都不是垂线\n",
    "            if k1 == k2 and b1 == b2 and min(start1[1], end1[1])<=max(start2[1], end2[1]) and min(start2[1], end2[1])<=max(start1[1], end1[1]):\n",
    "                #两直线斜率相同、截距相同，类似两条垂线时的判断\n",
    "                return [max(min(start1[0], end1[0]), min(start2[0], end2[0])), max(min(start1[1], end1[1]), min(start2[1], end2[1]))]\n",
    "            elif k1 != k2:#两直线斜率不同\n",
    "                x = (b2-b1)/(k1-k2)\n",
    "                y = k1*x+b1\n",
    "                if (start2[1]-y)*(end2[1]-y)<=0 and (start1[1]-y)*(end1[1]-y)<=0:\n",
    "                    return [x, y]\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        def func(start,end):\n",
    "            x1,y1 = start\n",
    "            x2,y2 = end\n",
    "            if x1==x2:return inf,-inf\n",
    "            k = (y2-y1)/(x2-x1)\n",
    "            b = (x2*y1-x1*y2)/(x2-x1)\n",
    "            return k,b\n",
    "        dots = collections.defaultdict(list)\n",
    "        tmp = [(x1,y1),(x2,y2),(x3,y3),(x4,y4)] = [start1,end1,start2,end2]\n",
    "        xmin,xmax,ymin,ymax = min(x1,x2),max(x1,x2),min(y1,y2),max(y1,y2)\n",
    "        # if not (((xmin<=x3<=xmax or xmin<=x4<=xmax) and (ymin<=y3<=ymax or ymin<=y4<=ymax)) or ((min(x3,x4)<=x1<=max(x3,x4) or min(x3,x4)<=x2<=max(x3,x4)) and (min(y3,y4)<=y1<=max(y3,y4) or min(y3,y4)<=y2<=max(y3,y4)))):\n",
    "        #     print(\"88888\",(xmin<=x3<=xmax or xmin<=x4<=xmax), (ymin<=y3<=ymax or ymin<=y4<=ymax))\n",
    "        #     return []\n",
    "        for x,y in tmp:\n",
    "            dots[x].append(y)\n",
    "        k1,b1 = func(start1,end1)\n",
    "        k2,b2 = func(start2,end2)\n",
    "\n",
    "        if k1==k2:\n",
    "            if b1==b2 and ((xmin<=x3<=xmax or xmin<=x4<=xmax) and (ymin<=y3<=ymax or ymin<=y4<=ymax)):\n",
    "                x = sorted([x1,x2,x3,x4])[1]\n",
    "                y = sorted([y1,y2,y3,y4])[1] if x1==x2==x3==x4 else dots[x][0]\n",
    "                return [round(x,6),round(y,6)]\n",
    "            else:\n",
    "                return []\n",
    "        if k1==inf:\n",
    "            x,y = x1,k2*x1+b2\n",
    "        elif k2==inf:\n",
    "            x,y = x3,k1*x3+b1\n",
    "        else:\n",
    "            x = (b2-b1)/(k1-k2)\n",
    "            y = k1*x+b1\n",
    "        print(x,y)\n",
    "        return [round(x,6),round(y,6)] if ymin<=y<=ymax and min(y3,y4)<=y<=max(y3,y4) else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        # 判断 (xk, yk) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "        # 这里的前提是 (xk, yk) 一定在「直线」(x1, y1)~(x2, y2) 上\n",
    "        def inside(x1, y1, x2, y2, xk, yk):\n",
    "            # 若与 x 轴平行，只需要判断 x 的部分\n",
    "            # 若与 y 轴平行，只需要判断 y 的部分\n",
    "            # 若为普通线段，则都要判断\n",
    "            return (x1 == x2 or min(x1, x2) <= xk <= max(x1, x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))\n",
    "        \n",
    "        def update(ans, xk, yk):\n",
    "            # 将一个交点与当前 ans 中的结果进行比较\n",
    "            # 若更优则替换\n",
    "            return [xk, yk] if not ans or [xk, yk] < ans else ans\n",
    "        \n",
    "        x1, y1 = start1\n",
    "        x2, y2 = end1\n",
    "        x3, y3 = start2\n",
    "        x4, y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "        # 判断 (x1, y1)~(x2, y2) 和 (x3, y3)~(x4, y3) 是否平行\n",
    "        if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):\n",
    "            # 若平行，则判断 (x3, y3) 是否在「直线」(x1, y1)~(x2, y2) 上\n",
    "            if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):\n",
    "                # 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    ans = update(ans, x3, y3)\n",
    "                # 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    ans = update(ans, x4, y4)\n",
    "                # 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    ans = update(ans, x1, y1)\n",
    "                # 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    ans = update(ans, x2, y2)\n",
    "            # 在平行时，其余的所有情况都不会有交点\n",
    "        else:\n",
    "            # 联立方程得到 t1 和 t2 的值\n",
    "            t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))\n",
    "            t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))\n",
    "            # 判断 t1 和 t2 是否均在 [0, 1] 之间\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        x1,y1,x2,y2,x3,y3,x4,y4=*start1,*end1,*start2,*end2\n",
    "        det=lambda a,b,c,d: a*d-b*c\n",
    "        d=det(x1-x2,x4-x3,y1-y2,y4-y3)\n",
    "        p=det(x4-x2,x4-x3,y4-y2,y4-y3)\n",
    "        q=det(x1-x2,x4-x2,y1-y2,y4-y2)\n",
    "        if d!=0:\n",
    "            lam,eta=p/d,q/d\n",
    "            if not (0<=lam<=1 and 0<=eta<=1):return []\n",
    "            return [lam*x1+(1-lam)*x2,lam*y1+(1-lam)*y2]\n",
    "        if p!=0 or q!=0: return []\n",
    "        t1,t2=sorted([start1,end1]),sorted([start2,end2])\n",
    "        if t1[1]<t2[0] or t2[1]<t1[0]:return []\n",
    "        return max(t1[0],t2[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        # 判断 (xk, yk) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "        # 这里的前提是 (xk, yk) 一定在「直线」(x1, y1)~(x2, y2) 上\n",
    "        def inside(x1, y1, x2, y2, xk, yk):\n",
    "            # 若与 x 轴平行，只需要判断 x 的部分\n",
    "            # 若与 y 轴平行，只需要判断 y 的部分\n",
    "            # 若为普通线段，则都要判断\n",
    "            return (x1 == x2 or min(x1, x2) <= xk <= max(x1, x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))\n",
    "        \n",
    "        def update(ans, xk, yk):\n",
    "            # 将一个交点与当前 ans 中的结果进行比较\n",
    "            # 若更优则替换\n",
    "            return [xk, yk] if not ans or [xk, yk] < ans else ans\n",
    "        \n",
    "        x1, y1 = start1\n",
    "        x2, y2 = end1\n",
    "        x3, y3 = start2\n",
    "        x4, y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "        # 判断 (x1, y1)~(x2, y2) 和 (x3, y3)~(x4, y3) 是否平行\n",
    "        if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):\n",
    "            # 若平行，则判断 (x3, y3) 是否在「直线」(x1, y1)~(x2, y2) 上\n",
    "            if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):\n",
    "                # 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    ans = update(ans, x3, y3)\n",
    "                # 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    ans = update(ans, x4, y4)\n",
    "                # 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    ans = update(ans, x1, y1)\n",
    "                # 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    ans = update(ans, x2, y2)\n",
    "            # 在平行时，其余的所有情况都不会有交点\n",
    "        else:\n",
    "            # 联立方程得到 t1 和 t2 的值\n",
    "            t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))\n",
    "            t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))\n",
    "            # 判断 t1 和 t2 是否均在 [0, 1] 之间\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        # 判断 (xk, yk) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "        # 这里的前提是 (xk, yk) 一定在「直线」(x1, y1)~(x2, y2) 上\n",
    "        def inside(x1, y1, x2, y2, xk, yk):\n",
    "            # 若与 x 轴平行，只需要判断 x 的部分\n",
    "            # 若与 y 轴平行，只需要判断 y 的部分\n",
    "            # 若为普通线段，则都要判断\n",
    "            return (x1 == x2 or min(x1, x2) <= xk <= max(x1, x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))\n",
    "        \n",
    "        def update(ans, xk, yk):\n",
    "            # 将一个交点与当前 ans 中的结果进行比较\n",
    "            # 若更优则替换\n",
    "            return [xk, yk] if not ans or [xk, yk] < ans else ans\n",
    "        \n",
    "        x1, y1 = start1\n",
    "        x2, y2 = end1\n",
    "        x3, y3 = start2\n",
    "        x4, y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "        # 判断 (x1, y1)~(x2, y2) 和 (x3, y3)~(x4, y3) 是否平行\n",
    "        if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):\n",
    "            # 若平行，则判断 (x3, y3) 是否在「直线」(x1, y1)~(x2, y2) 上\n",
    "            if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):\n",
    "                # 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    ans = update(ans, x3, y3)\n",
    "                # 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    ans = update(ans, x4, y4)\n",
    "                # 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    ans = update(ans, x1, y1)\n",
    "                # 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    ans = update(ans, x2, y2)\n",
    "            # 在平行时，其余的所有情况都不会有交点\n",
    "        else:\n",
    "            # 联立方程得到 t1 和 t2 的值\n",
    "            t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))\n",
    "            t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))\n",
    "            # 判断 t1 和 t2 是否均在 [0, 1] 之间\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        def inside(x1,y1,x2,y2,xk,yk):\n",
    "            return (x1 == x2 or min(x1,x2) <= xk <= max(x1,x2)) and (y1 == y2 or min(y1,y2) <= yk <= max(y1,y2))\n",
    "        def update(ans, xk, yk):\n",
    "            return [xk,yk] if not ans or [xk,yk] < ans else ans\n",
    "        x1,y1 = start1\n",
    "        x2,y2 = end1\n",
    "        x3,y3 = start2\n",
    "        x4,y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "\n",
    "        if (y4-y3)*(x2-x1) == (y2-y1)*(x4-x3):\n",
    "            if (y2 - y1) * (x3-x1) == (y3-y1)*(x2-x1):\n",
    "                if inside(x1,y1,x2,y2,x3,y3):\n",
    "                    ans = update(ans, x3,y3)\n",
    "                if inside(x1,y1,x2,y2,x4,y4):\n",
    "                    ans = update(ans, x4,y4)\n",
    "                if inside(x3,y3,x4,y4,x1,y1):\n",
    "                    ans = update(ans,x1,y1)\n",
    "                if inside(x3,y3,x4,y4,x2,y2):\n",
    "                    ans = update(ans,x2,y2)\n",
    "        else:\n",
    "            a = x2-x1\n",
    "            b = x3-x4\n",
    "            c = x3-x1\n",
    "            d = y2-y1\n",
    "            e = y3-y4\n",
    "            f = y3-y1\n",
    "            dom = a*e - b*d\n",
    "            t1 = (c*e-b*f)/dom\n",
    "            t2 = (a*f-d*c)/dom\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2-x1), y1+t1*(y2-y1)]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        def func(start,end):\n",
    "            x1,y1 = start\n",
    "            x2,y2 = end\n",
    "            if x1==x2:return inf,-inf\n",
    "            k = (y2-y1)/(x2-x1)\n",
    "            b = (x2*y1-x1*y2)/(x2-x1)\n",
    "            return k,b\n",
    "        dots = collections.defaultdict(list)\n",
    "        tmp = [(x1,y1),(x2,y2),(x3,y3),(x4,y4)] = [start1,end1,start2,end2]\n",
    "        xmin,xmax,ymin,ymax = min(x1,x2),max(x1,x2),min(y1,y2),max(y1,y2)\n",
    "        for x,y in tmp:\n",
    "            dots[x].append(y)\n",
    "        k1,b1 = func(start1,end1)\n",
    "        k2,b2 = func(start2,end2)\n",
    "\n",
    "        if k1==k2:\n",
    "            if b1==b2 and ((xmin<=x3<=xmax or xmin<=x4<=xmax) and (ymin<=y3<=ymax or ymin<=y4<=ymax)):\n",
    "                x = sorted([x1,x2,x3,x4])[1]\n",
    "                y = sorted([y1,y2,y3,y4])[1] if x1==x2==x3==x4 else dots[x][0]\n",
    "                return [round(x,6),round(y,6)]\n",
    "            else:\n",
    "                return []\n",
    "        if k1==inf:\n",
    "            x,y = x1,k2*x1+b2\n",
    "        elif k2==inf:\n",
    "            x,y = x3,k1*x3+b1\n",
    "        else:\n",
    "            x = (b2-b1)/(k1-k2)\n",
    "            y = k1*x+b1\n",
    "\n",
    "        return [round(x,6),round(y,6)] if ymin<=y<=ymax and min(y3,y4)<=y<=max(y3,y4) else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "sub   = lambda A, B: [A[0] - B[0], A[1] - B[1]]\n",
    "mul   = lambda k, A: [k * A[0], k * A[1]]\n",
    "cross = lambda A, B: A[0] * B[1] - A[1] * B[0]\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        A, B    = sorted([start1, end1])\n",
    "        C, D    = sorted([start2, end2])\n",
    "        a, b, u = sub(B, A), sub(D, C), sub(B, D)\n",
    "        x, y    = cross(a, b), cross(u, b)\n",
    "        if x == 0:\n",
    "            return max(A, C) if y == 0 and max(A, C) <= min(B, D) else []\n",
    "        E = sub(B, mul(y / x, a))\n",
    "        return E if A <= E <= B and C <= E <= D else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        def inside(x1,y1,x2,y2,xk,yk):\n",
    "            return (x1 == x2 or min(x1,x2) <= xk <= max(x1,x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))\n",
    "\n",
    "        def update(ans, xk, yk):\n",
    "            return [xk,yk] if not ans or [xk,yk]<ans else ans\n",
    "        \n",
    "        x1, y1 = start1\n",
    "        x2, y2 = end1\n",
    "        x3, y3 = start2\n",
    "        x4, y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "        # 判断 (x1, y1)~(x2, y2) 和 (x3, y3)~(x4, y3) 是否平行\n",
    "        if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):\n",
    "            # 若平行，则判断 (x3, y3) 是否在「直线」(x1, y1)~(x2, y2) 上\n",
    "            if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):\n",
    "                # 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    ans = update(ans, x3, y3)\n",
    "                # 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    ans = update(ans, x4, y4)\n",
    "                # 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    ans = update(ans, x1, y1)\n",
    "                # 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    ans = update(ans, x2, y2)\n",
    "        else:\n",
    "            # 联立方程得到 t1 和 t2 的值\n",
    "            t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))\n",
    "            t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))\n",
    "            # 判断 t1 和 t2 是否均在 [0, 1] 之间\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        line_A_x1, line_A_y1 = start1\n",
    "        line_A_x2, line_A_y2 = end1\n",
    "\n",
    "        line_B_x1, line_B_y1 = start2\n",
    "        line_B_x2, line_B_y2 = end2\n",
    "        \n",
    "        # 计算斜率\n",
    "        if line_A_x1 == line_A_x2:\n",
    "            K_line_A = None\n",
    "        else:\n",
    "            K_line_A = (line_A_y2 - line_A_y1) / (line_A_x2 - line_A_x1)\n",
    "        if line_B_x1 == line_B_x2:\n",
    "            K_line_B = None\n",
    "        else:\n",
    "            K_line_B = (line_B_y2 - line_B_y1) / (line_B_x2 - line_B_x1)\n",
    "        def solve(k, x0, y0, x):\n",
    "            y = y0 + k * (x - x0) + y0\n",
    "            return y\n",
    "        \n",
    "        # 两直线存在垂直的情况\n",
    "        if K_line_A is None or K_line_B is None:\n",
    "            # 两直线都垂直\n",
    "            if K_line_A is None and K_line_B is None:\n",
    "                ay1, ay2 = min(line_A_y1, line_A_y2), max(line_A_y1, line_A_y2)\n",
    "                by1, by2 = min(line_B_y1, line_B_y2), max(line_B_y1, line_B_y2)\n",
    "                if line_A_x1 == line_B_x1 and max(ay1, by1) <= min(ay2, by2):\n",
    "                    return [line_A_x1, max(line_A_y1, line_B_y1)]\n",
    "                else:\n",
    "                    return []\n",
    "            # 有一直线垂直\n",
    "            if K_line_A is None:\n",
    "                #y - line_B_y1 == k(x - lineb_x1)\n",
    "                if line_B_x1 <= line_A_x1 <= line_B_x2:\n",
    "                    solve_y = solve(K_line_B, line_B_x1, line_B_y1, line_A_x1)\n",
    "                    if max(line_A_y1, line_B_y1) <= solve_y <= min(line_A_y2, line_B_y2):\n",
    "                        return [line_A_x1, solve_y]\n",
    "                    else:\n",
    "                        return []\n",
    "                else:\n",
    "                    return []\n",
    "            # 有一直线垂直\n",
    "            if K_line_B is None:\n",
    "                #y - line_B_y1 == k(x - lineb_x1)\n",
    "                if line_A_x1 <= line_B_x1 <= line_A_x2:\n",
    "                    solve_y = solve(K_line_A, line_A_y1, line_A_y1, line_B_x1)\n",
    "                    if max(line_A_y1, line_B_y1) <= solve_y <= min(line_A_y2, line_B_y2):\n",
    "                        return [line_B_x1, solve_y]\n",
    "                    else:\n",
    "                        return []\n",
    "                else:\n",
    "                    return []\n",
    "        \n",
    "        # 两直线均不垂直\n",
    "        # Y = K1(x-xA0)+yA0\n",
    "        # Y = K2(x-xB0)+yB0\n",
    "        # K1(x-xA0)+yA0 = K2(x-xB0)+yB0\n",
    "        # (K1-K2)x = K2xB0+K1XA0+yB0-yA0\n",
    "        print(\"all not ver\")\n",
    "\n",
    "        #平行\n",
    "        if K_line_A == K_line_B:\n",
    "            if line_A_y1 - K_line_A*line_A_x1 == line_B_y1 - K_line_B * line_B_x1:\n",
    "                ay1, ay2 = min(line_A_y1, line_A_y2), max(line_A_y1, line_A_y2)\n",
    "                by1, by2 = min(line_B_y1, line_B_y2), max(line_B_y1, line_B_y2)\n",
    "                ax1, ax2 = min(line_A_x1, line_A_x2), max(line_A_x1, line_A_x2)\n",
    "                bx1, bx2 = min(line_B_x1, line_B_x2), max(line_B_x1, line_B_x2)                \n",
    "                if max(ax1, bx1) <= min(ax2, bx2) and max(ay1, by1) <= min(ay2, by2):\n",
    "                    return [max(line_A_y1, line_B_y1), max(line_A_y1, line_B_y1)]\n",
    "                else:\n",
    "                    return []\n",
    "            else:\n",
    "                return []\n",
    "        print(\"not px\")\n",
    "        x = (-K_line_B * line_B_x1 + K_line_A * line_A_x1 +line_B_y1 -line_A_y1) / (K_line_A - K_line_B)\n",
    "        y = K_line_A* (x - line_A_x1) + line_A_y1\n",
    "        ax1, ax2 = min(line_A_x1, line_A_x2), max(line_A_x1, line_A_x2)\n",
    "        bx1, bx2 = min(line_B_x1, line_B_x2), max(line_B_x1, line_B_x2)\n",
    "\n",
    "        if max(ax1, bx1) <= x <= min(ax2, bx2):\n",
    "            return [x, y]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        \"\"\"\n",
    "        # specical situation vertical\n",
    "        if end1[0] == start1[0] and end2[0] == start2[0]:\n",
    "            if end1[0] != end2[0]:\n",
    "                return []\n",
    "            else:\n",
    "                mn1, mx1 = min(start1[1], end1[1]), max(start1[1], end1[1])\n",
    "                mn2, mx2 = min(start2[1], end2[1]), max(start2[1], end2[1])\n",
    "\n",
    "                if mn1 > mx2 or mn2 < mx1:\n",
    "                    return []\n",
    "                elif mn1 <= mx2 and mn1 > mn2:\n",
    "                    return [end1[0], mn1]\n",
    "                elif mn2 <= mx1 and mn2 > mn1:\n",
    "                    return [end1[0], mn2]\n",
    "                \n",
    "\n",
    "        a1 = (end1[1]-start1[1]) / (end1[0] - start1[0])\n",
    "        b1 = start1[1] - (end1[1]-start1[1]) / (end1[0]-start1[0]) \n",
    "\n",
    "        a2 = (end2[1]-start2[1]) / (end2[0] - start2[0])\n",
    "        b2 = start2[1] - (end2[1]-start2[1]) / (end2[0]-start2[0])\n",
    "\n",
    "        if a1 == a2 and b1 == b2:\n",
    "\n",
    "            x = [start1[0], end1[0], start2[0], end2[0]]\n",
    "            y = [start1[1], end1[1], start2[1], end2[1]]\n",
    "\n",
    "            if a1 > 0 or a1 < 0:\n",
    "                mn = min(x)\n",
    "                idx = x.index(mn)\n",
    "                return [mn, y[idx]]\n",
    "            else:\n",
    "                mx = max(y)\n",
    "                idx = y.index(mx)\n",
    "                return [x[idx], mx]\n",
    "\n",
    "        else:\n",
    "            cross_dotx = (b2-b1)/(a1-a2)\n",
    "\n",
    "            if cross_dotx>=start1[0] and cross_dotx<=end1[0]:\n",
    "                cross_doty = a1 * cross_dotx + b1\n",
    "                return [cross_dotx, cross_doty]\n",
    "            else:\n",
    "                return []\n",
    "        \"\"\"\n",
    "\n",
    "\n",
    "        def inside(x1, y1, x2, y2, xk, yk):\n",
    "            return (x1 == x2 or min(x1, x2) <= xk <= max(x1, x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))\n",
    "        \n",
    "        def update(ans, xk, yk):\n",
    "            return [xk, yk] if not ans or [xk, yk] < ans else ans\n",
    "\n",
    "        x1, y1 = start1\n",
    "        x2, y2 = end1\n",
    "        x3, y3 = start2\n",
    "        x4, y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "        if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):\n",
    "            if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    ans = update(ans, x3, y3)\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    ans = update(ans, x4, y4)\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    ans = update(ans, x1, y1)\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    ans = update(ans, x2, y2)\n",
    "        else:\n",
    "            t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))\n",
    "            t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        # 判断 (xk, yk) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "        # 这里的前提是 (xk, yk) 一定在「直线」(x1, y1)~(x2, y2) 上\n",
    "        def inside(x1, y1, x2, y2, xk, yk):\n",
    "            # 若与 x 轴平行，只需要判断 x 的部分\n",
    "            # 若与 y 轴平行，只需要判断 y 的部分\n",
    "            # 若为普通线段，则都要判断\n",
    "            return (x1 == x2 or min(x1, x2) <= xk <= max(x1, x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))\n",
    "        \n",
    "        def update(ans, xk, yk):\n",
    "            # 将一个交点与当前 ans 中的结果进行比较\n",
    "            # 若更优则替换\n",
    "            return [xk, yk] if not ans or [xk, yk] < ans else ans\n",
    "        \n",
    "        x1, y1 = start1\n",
    "        x2, y2 = end1\n",
    "        x3, y3 = start2\n",
    "        x4, y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "        # 判断 (x1, y1)~(x2, y2) 和 (x3, y3)~(x4, y3) 是否平行\n",
    "        if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):\n",
    "            # 若平行，则判断 (x3, y3) 是否在「直线」(x1, y1)~(x2, y2) 上\n",
    "            if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):\n",
    "                # 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    ans = update(ans, x3, y3)\n",
    "                # 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    ans = update(ans, x4, y4)\n",
    "                # 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    ans = update(ans, x1, y1)\n",
    "                # 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    ans = update(ans, x2, y2)\n",
    "            # 在平行时，其余的所有情况都不会有交点\n",
    "        else:\n",
    "            # 联立方程得到 t1 和 t2 的值\n",
    "            t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))\n",
    "            t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))\n",
    "            # 判断 t1 和 t2 是否均在 [0, 1] 之间\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef intersection(self, start1, end1, start2, end2):\n",
    "\t\tif start1[0] > end1[0]:\n",
    "\t\t\tstart1, end1 = end1, start1\n",
    "\t\tif start2[0] > end2[0]:\n",
    "\t\t\tstart2, end2 = end2, start2\n",
    "\t\tif max(start1[0], start2[0]) > min(end1[0], end2[0]):\n",
    "\t\t\treturn []\n",
    "\t\tif start1 == end1 == start2 == end2: #4点重合\n",
    "\t\t\treturn start1\n",
    "\t\tif start1 == end1: #2点重合在另一线段上\n",
    "\t\t\treturn start1 if (start1[0] - start2[0]) * (start2[1] - end2[1]) == (start1[1] - start2[1]) * (start2[0] - end2[0]) else []\n",
    "\t\tif start2 == end2:\n",
    "\t\t\treturn start2 if (start2[0] - start1[0]) * (start1[1] - end1[1]) == (start2[1] - start1[1]) * (start1[0] - end1[0]) else []\n",
    "\t\ta1, b1, c1 = self.calc(start1, end1)\n",
    "\t\ta2, b2, c2 = self.calc(start2, end2)\n",
    "\t\tif a1 * b2 == a2 * b1: #直线平行\n",
    "\t\t\tif a1 * c2 == a2 * c1: #直线重合\n",
    "\t\t\t\tx, y = max(start1, start2)\n",
    "\t\t\telse:\n",
    "\t\t\t\treturn []\n",
    "\t\telse:\n",
    "\t\t\tx = (c1 * b2 - c2 * b1) / (a2 * b1 - a1 * b2)\n",
    "\t\t\ty = -(c1 + a1 * x) / b1 if b1 != 0 else -(c2 + a2 * x) / b2\n",
    "\t\treturn [x, y] if self.chk(start1, end1, x, y) and self.chk(start2, end2, x, y) else []\n",
    "\t\n",
    "\tdef calc(self, p1, p2):\n",
    "\t\tif p1[0] == p2[0]:\n",
    "\t\t\treturn [1, 0, -p1[0]]\n",
    "\t\tif p1[1] == p2[1]:\n",
    "\t\t\treturn [0, 1, -p1[1]]\n",
    "\t\tdx = p2[0] - p1[0]\n",
    "\t\tdy = p2[1] - p1[1]\n",
    "\t\treturn [dy, -dx, dx * p1[1] - dy * p1[0]]\n",
    "\t\n",
    "\tdef chk(self, p1, p2, x, y):\n",
    "\t\treturn min(p1[0], p2[0]) <= x <= max(p1[0], p2[0]) and min(p1[1], p2[1]) <= y <= max(p1[1], p2[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = set(nums[0])\n",
    "        for i in range(1, n):\n",
    "            tmp = set()\n",
    "            for num in nums[i]:\n",
    "                if num in res:\n",
    "                    tmp.add(num)\n",
    "            res = tmp\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = set(nums[0])\n",
    "        for i in range(1, n):\n",
    "            tmp = set()\n",
    "            for num in nums[i]:\n",
    "                if num in res:\n",
    "                    tmp.add(num)\n",
    "            res = tmp        \n",
    "        return sorted(res)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = nums[0]\n",
    "        for i in range(1, n):\n",
    "            tmp = set()\n",
    "            for num in nums[i]:\n",
    "                if num in res:\n",
    "                    tmp.add(num)\n",
    "            res = tmp\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = nums[0]\n",
    "        for i in range(1, n):\n",
    "            tmp = set()\n",
    "            for num in nums[i]:\n",
    "                if num in res:\n",
    "                    tmp.add(num)\n",
    "            res = tmp\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        #题解测试\n",
    "        return sorted(reduce(set.__iand__, map(set, nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        times={i:1 for i in nums[0]}\n",
    "        a=[]\n",
    "        for i in nums[1:]:\n",
    "            for j in i:\n",
    "                if j in times:\n",
    "                    times[j]+=1\n",
    "                else:\n",
    "                    times[j]=1\n",
    "        Len=len(nums)\n",
    "        for i,t in times.items():\n",
    "            if t==Len:\n",
    "                a.append(i)\n",
    "        else:\n",
    "            a.sort()\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        res = nums[0]\n",
    "        for num in nums:\n",
    "            for i in res[:]:\n",
    "                if i not in num:\n",
    "                    res.remove(i)\n",
    "        res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = nums[0]\n",
    "        for i in range(1, n):\n",
    "            tmp = set()\n",
    "            for num in nums[i]:\n",
    "                if num in res:\n",
    "                    tmp.add(num)\n",
    "            res = tmp\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        array = [0] * 1001\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            for j, a in enumerate(num):\n",
    "                array[a] += 1\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(len(array)):\n",
    "            if array[i] == n:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        n=nums[0]\n",
    "        for i in range(len(nums)):\n",
    "            n=[o for o in n if o in nums[i]]\n",
    "        return sorted(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        lookup = {}\n",
    "        for i in range(n):\n",
    "            for item in nums[i]:\n",
    "                if item not in lookup:\n",
    "                    lookup[item] = 1\n",
    "                else:\n",
    "                    lookup[item] += 1\n",
    "        ans = []\n",
    "        for key, value in lookup.items():\n",
    "            if value == n:\n",
    "                ans.append(key)\n",
    "        if not ans:\n",
    "            return ans\n",
    "        def quicksort(nums, left, right):\n",
    "            if left >= right:return\n",
    "            i, j = left, right\n",
    "            while i < j:\n",
    "                while i < j and nums[j] >= nums[left]: j -= 1\n",
    "                while i < j and nums[i] <= nums[left]: i += 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "            nums[i], nums[left] = nums[left], nums[i]\n",
    "            quicksort(nums, left, i - 1)\n",
    "            quicksort(nums, i + 1, right)\n",
    "        quicksort(ans, 0, len(ans) - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from string import *\n",
    "from re import *\n",
    "from datetime import *\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from bisect import *\n",
    "from copy import *\n",
    "from math import *\n",
    "from random import *\n",
    "from statistics import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from operator import *\n",
    "from io import *\n",
    "from sys import *\n",
    "from json import *\n",
    "from builtins import *\n",
    "from typing import *\n",
    "\n",
    "\"\"\"\n",
    "Given a 2D integer array nums where nums[i] is a non-empty array of distinct positive integers,\n",
    "return the list of integers that are present in each array of nums sorted in ascending order.\n",
    "\n",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "\n",
    "Input: nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]\n",
    "Output: [3,4]\n",
    "Explanation: \n",
    "The only integers present in each of nums[0] = [3,1,2,4,5], nums[1] = [1,2,3,4], and nums[2] = [3,4,5,6] are 3 and 4, so we return [3,4].\n",
    "\n",
    "Example 2:\n",
    "\n",
    "\n",
    "Input: nums = [[1,2,3],[4,5,6]]\n",
    "Output: []\n",
    "Explanation: \n",
    "There does not exist any integer present both in nums[0] and nums[1], so we return an empty list [].\n",
    "\n",
    "\n",
    " \n",
    "\n",
    "Constraints:\n",
    "\n",
    " * 1 <= nums.length <= 1000\n",
    " * 1 <= sum(nums[i].length) <= 1000\n",
    " * 1 <= nums[i][j] <= 1000\n",
    " * All the values of nums[i] are unique.\n",
    "\"\"\"\n",
    "\n",
    "MOD = 1000000007 # 998244353\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        return list(sorted(reduce(and_, map(set, nums))))\n",
    "\n",
    "# testcases = [\n",
    "#     [],\n",
    "#     # [],\n",
    "# ]\n",
    "\n",
    "# s = Solution()\n",
    "# func_name = dir(s)[-1]\n",
    "# func = getattr(s, func_name)\n",
    "\n",
    "# for args in testcases:\n",
    "#     print(func(*args))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        cnt = Counter([x for num in nums for x in num])\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        for v, c in cnt.items():\n",
    "            if c == n:\n",
    "                ans.append(v)\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        num = set(min(nums,key=len))\n",
    "        for i in num:\n",
    "            if all(i in nums[x] for x in range(len(nums))):\n",
    "                res.append(i)\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        res = set(nums[0])\n",
    "        for num in nums:\n",
    "            temp = set()\n",
    "            for i in num:\n",
    "                if i in res:\n",
    "                    temp.add(i)\n",
    "            res = temp\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        # 用集合试试  92%\n",
    "        # n = len(nums)\n",
    "        # tm = [i for i in range(1, 1000+1)]\n",
    "        # tm = set(tm)\n",
    "        # for i in range(n):\n",
    "        #         s = set(nums[i])\n",
    "        #         tm = tm&s\n",
    "        # tm = list(tm)\n",
    "        # tm.sort()\n",
    "        # return tm\n",
    "\n",
    "\n",
    "        #官解\n",
    "        n = len(nums)\n",
    "        res = set(nums[0])\n",
    "        for i in range(1, n):\n",
    "            tm = set()\n",
    "            for nu in nums[i]:\n",
    "                if nu in res:\n",
    "                    tm.add(nu)\n",
    "            res = tm\n",
    "        return sorted(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = set(nums[0])\n",
    "        for i in range(1, n):\n",
    "            tmp = set()\n",
    "            for num in nums[i]:\n",
    "                if num in res:\n",
    "                    tmp.add(num)\n",
    "            res = tmp\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        x = set(nums[0])\n",
    "        for i in nums[1:]:\n",
    "            x &= set(i)\n",
    "        return sorted(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        times={i:1 for i in nums[0]}\n",
    "        a=[]\n",
    "        for i in nums[1:]:\n",
    "            for j in i:\n",
    "                if j in times:\n",
    "                    times[j]+=1\n",
    "                else:\n",
    "                    times[j]=1\n",
    "        Len=len(nums)\n",
    "        for i,t in times.items():\n",
    "            if t==Len:\n",
    "                a.append(i)\n",
    "        else:\n",
    "            a.sort()\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        array = [0] * 1001\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            for j, a in enumerate(num):\n",
    "                array[a] += 1\n",
    "        \n",
    "        ans = []\n",
    "        for i, a in enumerate(array):\n",
    "            if array[i] == n:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        res = nums[0]\n",
    "        for num in nums:\n",
    "            for i in res[:]:\n",
    "                if i not in num:\n",
    "                    res.remove(i)\n",
    "        # res.sort()\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        tmp = []\n",
    "        for i in nums[0]:\n",
    "            back = True\n",
    "            for j in range(1, len(nums)):\n",
    "                if i not in nums[j]: back = False\n",
    "\n",
    "            if back == True: tmp.append(i)\n",
    "            tmp.sort()\n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce \n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        return sorted(k for k, v in Counter(sum(nums, [])).items() if v == len(nums))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        num = min(nums,key=len)\n",
    "        for i in num:\n",
    "            if all(i in nums[x] for x in range(len(nums))):\n",
    "                res.append(i)\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = nums[0]\n",
    "        for i in range(1, n):\n",
    "            tmp = set()\n",
    "            for num in nums[i]:\n",
    "                if num in res:\n",
    "                    tmp.add(num)\n",
    "            res = tmp\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        return sorted(reduce (lambda x,y: set(x) & set(y),nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = set(nums[0])\n",
    "        for i in range(1,n):\n",
    "            tmp = set()\n",
    "            for num in nums[i]:\n",
    "                if num in res:\n",
    "                    tmp.add(num)\n",
    "            res = tmp\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        l = []\n",
    "        for i in range(len(nums[0])):\n",
    "            f = 0\n",
    "            for j in range(len(nums)):\n",
    "                if nums[0][i] in nums[j]:\n",
    "                    f = f+1\n",
    "            if f==len(nums):\n",
    "                l.append(nums[0][i])\n",
    "        l.sort()\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        res=set()\n",
    "        for i in range(len(nums)):\n",
    "            t=nums[:i]+nums[i+1:]\n",
    "            for j in nums[i]:\n",
    "                flag=True                \n",
    "                for m in t:\n",
    "                    if j not in m:\n",
    "                        flag=False\n",
    "                if flag:\n",
    "                    res.add(j)\n",
    "        res=list(res)\n",
    "        res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        cnt = [0 for i in range(1002)]\n",
    "        for num in nums:\n",
    "            for i in num:\n",
    "                cnt[i] += 1\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        for i in range(1, 1002):\n",
    "            if cnt[i] == n:\n",
    "                res.append(i)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        res=[]\n",
    "        for i in range(len(nums)):\n",
    "            t=nums[:i]+nums[i+1:]\n",
    "            for j in nums[i]:\n",
    "                flag=True                \n",
    "                for m in t:\n",
    "                    if j not in m:\n",
    "                        flag=False\n",
    "                if flag:\n",
    "                    res.append(j)\n",
    "        res=list(set(res))\n",
    "        res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        ans = set(nums[0])\n",
    "        for num in nums[1:]:\n",
    "            ans = ans & set(num)\n",
    "        ans = list(ans)\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        c1=Counter(nums[0])\n",
    "        for i in nums:\n",
    "            c2=Counter(i)\n",
    "            c1=c1&c2\n",
    "        l=[]\n",
    "        for i in c1:\n",
    "            for j in range(c1[i]):\n",
    "                l+=[i]\n",
    "        return sorted(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        ns = []\n",
    "        for i in nums[0]:\n",
    "            present = True\n",
    "            for j in range(1,len(nums)):\n",
    "                if i not in nums[j]:\n",
    "                    present = False\n",
    "                    break\n",
    "            if present:\n",
    "                ns.append(i)\n",
    "        ns.sort()\n",
    "        return ns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        max_num = max([max(l) for l in nums])\n",
    "        counts = [0]*max_num\n",
    "        for i in range(1,max_num+1):\n",
    "            for n in nums:\n",
    "                if i in n:\n",
    "                    counts[i-1] += 1\n",
    "        ns = []\n",
    "        for i in range(max_num):\n",
    "            if counts[i] == len(nums):\n",
    "                ns.append(i+1)\n",
    "        return ns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        count = defaultdict(int)\n",
    "        for arr in nums:\n",
    "            for i in range(len(arr)):\n",
    "                count[arr[i]] += 1\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        for key in count:\n",
    "            if count[key] == n:\n",
    "                ans.append(key)\n",
    "        \n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        x = len(nums)\n",
    "        for i in nums[0]:\n",
    "            b = True\n",
    "            for j in range(1,x):\n",
    "                if i not in nums[j]:\n",
    "                    b = False\n",
    "                    break\n",
    "            if b:\n",
    "                res.append(i)\n",
    "        res1 = sorted(res)\n",
    "        return res1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        newNums = set(nums[0])\n",
    "        for i in range(1,len(nums)):\n",
    "            newNums = newNums & set(nums[i])\n",
    "        return sorted(list(newNums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        freq = {}\n",
    "        n = len(nums)\n",
    "        for arr in nums:\n",
    "            for num in arr:\n",
    "                if num in freq.keys():\n",
    "                    freq[num] += 1\n",
    "                else:\n",
    "                    freq[num] = 1\n",
    "        ans = []\n",
    "        for k,v in freq.items():\n",
    "            if v == n:\n",
    "                ans.append(k)\n",
    "        return sorted(ans)\n",
    "        \n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        list_,len_=[],len(nums)\n",
    "        nums[0].sort()\n",
    "        for j in nums[0]:\n",
    "            a=0\n",
    "            for i in range(1,len_):            \n",
    "                if j not in nums[i]:\n",
    "                    a=1\n",
    "                    break\n",
    "            if a==0:\n",
    "                list_.append(j)\n",
    "        return list_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        inters = set(nums[0])\n",
    "        for i in range(1, n):\n",
    "            inters = inters.intersection(nums[i])\n",
    "        return sorted(list(inters))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        num = min(nums,key=len)\n",
    "        for i in num:\n",
    "            if all(i in nums[x] for x in range(len(nums))):\n",
    "                res.append(i)\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        dic = dict()\n",
    "        for num in nums:\n",
    "            num = set(num)\n",
    "            for n in num:\n",
    "                if n not in dic.keys():\n",
    "                    dic[n] = 1\n",
    "                else:\n",
    "                    dic[n] += 1\n",
    "        ans = []\n",
    "        ks = list(dic.keys())\n",
    "        vs = list(dic.values())\n",
    "        for i in range(len(ks)):\n",
    "            if vs[i] == len(nums):\n",
    "                ans.append(ks[i])\n",
    "\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        res = set(nums[0])\n",
    "        for i in range(1, len(nums)):\n",
    "            temp = set()\n",
    "            for num in nums[i]:\n",
    "                if num in res:\n",
    "                    temp.add(num)\n",
    "            res = temp\n",
    "\n",
    "        return sorted(list(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        interset = set(nums[0])\n",
    "        for item in nums[1:]:\n",
    "            interset = interset & set(item)\n",
    "        ans = sorted(list(interset))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        hash_set = set()\n",
    "        for num in nums[0]:\n",
    "            hash_set.add(num)\n",
    "        for i in range(1, len(nums)):\n",
    "            res = []\n",
    "            for num in nums[i]:\n",
    "                if num in hash_set:\n",
    "                    res.append(num)\n",
    "            hash_set = set(res)\n",
    "        res = list(hash_set)\n",
    "        res.sort()\n",
    "        return res\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = set(nums[0])\n",
    "        for i in range(1, n):\n",
    "            tmp = set()\n",
    "            for num in nums[i]:\n",
    "                if num in res:\n",
    "                    tmp.add(num)\n",
    "            res = tmp\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        if not nums:\n",
    "            return []\n",
    "        s = set(nums[0])\n",
    "        for i in range(1, len(nums)):\n",
    "            s = s & set(nums[i])\n",
    "        if s:\n",
    "            l = list(s)\n",
    "            l.sort()\n",
    "            return l\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        nums2=[]\n",
    "        for i in nums[0]:\n",
    "            a=0\n",
    "            for j in nums:\n",
    "                if i not in j:\n",
    "                    a+=1\n",
    "            if a==0:\n",
    "                nums2.append(i)\n",
    "        nums2.sort()\n",
    "        return nums2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        return sorted(list(reduce(lambda x,y: set(x) & set(y), nums)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        return sorted(reduce(and_, map(lambda x : set(x), nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        times={i:1 for i in nums[0]}\n",
    "        a=[]\n",
    "        for i in nums[1:]:\n",
    "            for j in i:\n",
    "                if j in times:\n",
    "                    times[j]+=1\n",
    "                else:\n",
    "                    times[j]=1\n",
    "        Len=len(nums)\n",
    "        for i,t in times.items():\n",
    "            if t==Len:\n",
    "                a.append(i)\n",
    "        else:\n",
    "            a.sort()\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        s = set(nums[0])\n",
    "        for num in nums[1:]:\n",
    "            s &= set(num)\n",
    "        return sorted(list(s))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        ans = set(nums[0])\n",
    "        for ns in nums[1:]:\n",
    "            ans = ans.intersection(set(ns))\n",
    "        return sorted(list(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = set(nums[0])\n",
    "        for i in range(1, n):\n",
    "            tmp = set()\n",
    "            for num in nums[i]:\n",
    "                if num in res:\n",
    "                    tmp.add(num)\n",
    "            res = tmp\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = set(nums[0])\n",
    "        for i in range(1, n):\n",
    "            tmp = set()\n",
    "            for num in nums[i]:\n",
    "                if num in res:\n",
    "                    tmp.add(num)\n",
    "            res = tmp\n",
    "        return sorted(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        mp = dict()\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums[i])):\n",
    "                if nums[i][j] not in mp.keys():\n",
    "                    mp[nums[i][j]] = 1\n",
    "                else:\n",
    "                    mp[nums[i][j]] += 1\n",
    "        ans = []\n",
    "        for k, v in mp.items():\n",
    "            if v == len(nums):\n",
    "                ans.append(k)\n",
    "        \n",
    "        return sorted(ans)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        ans = set(nums[0])\n",
    "        for x in nums:\n",
    "            ans &= set(x)\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        # 特殊情况列表长度为1\n",
    "        length = len(nums)\n",
    "        if length == 1:\n",
    "            nums[0].sort()\n",
    "            return nums[0]\n",
    "        # 正常情况。两个相邻列表相比\n",
    "        start = 0\n",
    "        end = 1\n",
    "        start_list = nums[start]\n",
    "        while end < len(nums):\n",
    "            start_list = [x for x in start_list if x in nums[end]]\n",
    "            if not start_list:\n",
    "                return []\n",
    "            end += 1\n",
    "        # 错误点升序排列的数组\n",
    "        start_list.sort()\n",
    "        return start_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        nums_len=len(nums)\n",
    "        counter = defaultdict(int)\n",
    "        for num in nums:\n",
    "            for n in num:\n",
    "                counter[n]+=1\n",
    "        ans = []\n",
    "        for k,v in counter.items():\n",
    "            if v==nums_len:\n",
    "                ans.append(k)\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        s = set(nums[0])\n",
    "        for i in range(1, n):\n",
    "            s = s & set(nums[i])\n",
    "        l = list(s)\n",
    "        l.sort()\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        ans = set(nums[0])\n",
    "        for x in range(1,len(nums)):\n",
    "            ans &= set(nums[x])\n",
    "        return sorted(list(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        return sorted(reduce(lambda a,b: set(a) & set(b), nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        freq={}\n",
    "        for arr in nums:\n",
    "            for num in arr:\n",
    "                if num in freq:\n",
    "                    freq[num]+=1\n",
    "                else:\n",
    "                    freq[num]=1\n",
    "        res=[] \n",
    "        for k,v in freq.items():\n",
    "            if v==n:\n",
    "                res.append(k)\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        res = set(nums[0])\n",
    "        for i in nums:\n",
    "            res = res & set(i)\n",
    "        res = list(res)\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        nums = [set(x) for x in nums]\n",
    "        res = set(nums[0])\n",
    "        for x in nums[1:]:\n",
    "            res &= x\n",
    "        return sorted(list(res))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        # 用集合试试\n",
    "        n = len(nums)\n",
    "        tm = [i for i in range(1, 1000+1)]\n",
    "        tm = set(tm)\n",
    "        for i in range(n):\n",
    "                s = set(nums[i])\n",
    "                tm = tm&s\n",
    "        tm = list(tm)\n",
    "        tm.sort()\n",
    "        return tm\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        res = set(nums[0])\n",
    "        for i in range(len(nums)):\n",
    "            n = set(nums[i])\n",
    "            res = n & res\n",
    "        return sorted(list(res))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\n",
    "        dic = dict()\n",
    "        for num in nums:\n",
    "            num = set(num)\n",
    "            for n in num:\n",
    "                if n not in dic.keys():\n",
    "                    dic[n] = 1\n",
    "                else:\n",
    "                    dic[n] += 1\n",
    "        ans = []\n",
    "        ks = list(dic.keys())\n",
    "        vs = list(dic.values())\n",
    "        for i in range(len(ks)):\n",
    "            if vs[i] == len(nums):\n",
    "                ans.append(ks[i])\n",
    "\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\r\n",
    "        ans = set(nums[0])\r\n",
    "        for i in range(1, len(nums)):\r\n",
    "            ans = ans.intersection(nums[i])\r\n",
    "            if len(ans) == 0:\r\n",
    "                break\r\n",
    "        \r\n",
    "        return  sorted(list(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def intersection(self, nums: List[List[int]]) -> List[int]:\r\n",
    "        ans = set(nums[0])\r\n",
    "        for i in range(1, len(nums)):\r\n",
    "            ans = ans.intersection(nums[i])\r\n",
    "            if len(ans) == 0:\r\n",
    "                break\r\n",
    "        \r\n",
    "        return  sorted(list(ans))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
